王川：深度学习有多深？（二十一） 双陆棋和神经网络

本文是

的续篇.

    (1)

所有没有成熟的新理论，新技术出现之初，学术界都会有两派:

好派 （人工智能，增强学习就是好, 就是好！）

    和

P 派 （人工智能，增强学习好个 P,  好个 P ! )

P 派对增强学习理论最为诟病之处：不实用，然并卵.

迄今为止关于各种算法的讨论，都离不开一个核心概念： 价值函数.

简单说，在贝尔曼方程里面，价值函数就是目前状态的理论最大值。（参见这篇老文章 王川: 深度学习有多深? (十九) -- 维度的诅咒和蒙特-卡洛模拟）

在漂亮的公式背后，如何求解价值函数，是个大问题。早期教科书里的简单例子中，价值函数就是一个表格. 每个状态，表格里对应一个函数值，在模拟和学习中不断更新.

但对于稍微复杂的问题，状态空间极大，表格根本不实用.

以围棋为例，一盘棋下完，每步棋平均有 250个选择，落棋之后平均还会走 150步，状态空间约等于 250 的150次方。 这个数字已经远超过宇宙里的原子的数目 （有估算是 10的 80次方）。计算量之大，即使用前面提到的蒙特-卡洛模拟，也无法胜任.

怎么办？解决方法是： 近似， 近似， 近似.

    (2)

如何近似价值函数?

如果你还记得这篇老文章

86年以后，随着反向传播算法的发明，神经网络的研究开始复苏.

一些研究者，开始使用神经网络用于价值函数的近似计算.

奥地利学者 Kurt Hornik 在1991年的论文里，曾经证明，一个前馈神经网络，可以近似任何连续的非线性的函数。增加近似的精度，可以依靠增加神经元的数目实现.

神经网络用于价值函数的近似计算，它的一个优点，是相对于神经元连接的各个参数可以微分求导。通用的计算方法，是计算神经网络拟合的函数值，和实际值的方差，求导，然后使用所谓的“随机梯度下降” (Stochastic Gradient Descent) 的方法把方差最小化。

神经网络，和时间差分算法，第一个在实用上的突破，来自西洋双陆棋.

    (3)

西洋双陆棋 （Backgammon)，是一个有着五千年历史的古老游戏。对弈双方各有15个棋子，每次靠掷两个骰子决定移动棋子的步数，最先把棋子全部转移到对方区域者，获胜.

双陆棋上世纪六十年代在美国开始流行，1967年在赌城拉斯维加斯开始了第一次世界锦标赛.

1992年，IBM的研究员 Gerald Tesauro 开发了一个结合时间差分学习 （TD Learning）和神经网络的算法，给它取名 TD-Gammon,  专攻双陆棋.

 TD-gammon 使用了一个三层神经网络，如下图，棋盘状态由198个神经元代表，为输入端。中间的隐层有40-80个神经元，最后的输出值是价值函数的估算.

TD-gammon 最初版本，中间的隐层只有40个神经元，通过自己和自己下棋提高水平。每走一步，用时间差分算法，根据价值函数估算的差值，重新微调神经网络的参数。经过三十万个棋局的自我训练后，它达到了此前表现最好的电脑程序的水平。

此后改进版的算法，把隐层神经元数目增加到80，经过一百五十万次棋局的训练后，达到了和当时世界一流选手同等的水平.

TD-gammon 的另外一个收获是，在开局的落子上，发现了另外一种被所有前人忽略的走法，比传统走法要略优。这个新的开局走法，后被参加锦标赛的选手广泛采纳.

电脑发现了比人们的几百年，几千年来的定势思维更高明的策略, 这个现象之后将不断重复。

    (4)

从 TD-gammon 算法的成功，已经隐约可以看到一个有趣的现象:

生物进化的历史, 好似算法和计算能力提高的历史.

拥有抽象的近似计算能力，只要超越对手一点点，只要进步速度比对手更快, 就可以在生存竞争中胜出，更大概率的把基因传递到下一代.

Tesauro 之后有许多研究者试图把类似 TD-gammon 的算法用到象棋，围棋和其它游戏上，但是效果并不显著。主流的看法是，因为双陆棋每个回合都要掷骰子，游戏有较大的随机性，恰好和 TD-gammon 的算法合拍. 双陆棋的成功是个特例.

增强学习从理论到计算能力上，还有太多问题要解决，差距要弥补.

"好派"阵营继续壮大，但 "P派" 底子厚，仍然不为所动.

(未完待续)

==============================

点击下面链接获得本公众号的介绍

在投资和事业发展的路上如何集思广益，举重若轻？欢迎加入王川的俱乐部，这是一个凝聚来自世界四大洲各行各业精英的高端收费社区.有意入会者请和王川（微信号: 9935070) 直接联系。

作者简介：王川，投资人，中科大少年班校友，现居加州硅谷。个人微信号9935070,公众号 investguru ,新浪微博“硅谷王川"，知乎专栏 "兵无常势". 文章表达个人观点仅供参考，不构成对所述资产投资建议，投资有风险，入市须谨慎.

<王川自选集> 第一卷电子书，现可在百度云盘上免费下载，订阅本公众号后,在公众号菜单右下角点击"电子书", 即可获得下载指令. 总共收录我过去一年五十多篇原创的财经科技评论文章，近三百页，欢迎下载传阅！)

长按下面二维码订阅本公众号. 订阅后输入'目录‘两字看看你错过了多少好文章!